package com.lihepeng.leecode.tree;

/**
 * 二叉树的直径
 * 任意两个节点之间的路径长度 最长至今不一定穿过根节点
 * 每一条二叉树 的直径长度就是节点左右子树的最大深度之和
 */
public class Solution543 {
    private int maxDiameter = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        maxDepth(root);
        return maxDiameter;
    }

    private int maxDepth(TreeNode root) {
        if (root==null) {
            return 0 ;
        }
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        int calDiameter = left+right;
        maxDiameter = Math.max(maxDiameter,calDiameter);
        return 1+Math.max(left,right)+1;
    }

}
